package gold.digger;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC560 {

    public int subarraySum(int[] arr, int k) {
        Map<Long, Integer> dict = new HashMap<>();
        long curSum = 0L;
        int res = 0;
        dict.put(0L, 1);

        for (int i = 0; i < arr.length; i++) {
            curSum += arr[i];
            long subSum = curSum - k;
            if (dict.containsKey(subSum)) {
                res += dict.get(subSum);
            }

            dict.put(curSum, dict.getOrDefault(curSum, 0) + 1);
        }

        return res;
    }


    public static void main(String[] args) {
        LC560 an = new LC560();
        int[] arr = {0, 0, 0};

        System.out.println(an.subarraySum(arr, 0));
    }
}
